#include <stdio.h>
#include <string.h>
#include <strings.h>

#define NMAX 50000

typedef struct Node {
	char key;
	Node *prev,
	     *next;
} Node;

typedef struct List {
	Node nodes[NMAX+1];
	Node *begin, *end;
	Node *freeTop;
	Node *HEAD;
} List;


void
Init(List *lst)
{
	register int i;
	Node *node = &lst->nodes[0];

	node->prev = node;
	node->next = node;
	lst->begin = node;
	lst->end   = node;

	lst->freeTop = &lst->nodes[1];
	for (i = 1 ; i < NMAX ; ++i)
		lst->nodes[i].next = &lst->nodes[i+1];
	lst->nodes[NMAX].next = NULL;
}

Node*
Insert(List *lst, Node *node, int key)
{
	Node *newNode = lst->freeTop;

	lst->freeTop  = lst->freeTop->next;
	newNode->key  = key;
	newNode->prev = node->prev;
	newNode->next = node;

	newNode->prev->next = newNode;
	node->prev          = newNode;

	if (node == lst->begin)
		lst->begin = newNode;

	return newNode;
}

unsigned char
IsEmpty(const List *lst)
{
	return lst->begin->next == lst->end;
}

Node*
Delete(List * lst, Node * node)
{
	Node *nx = node->next,
	     *pr = node->prev;

	node->next   = lst->freeTop;
	lst->freeTop = node;
	pr->next = nx;
	nx->prev = pr;
	if (node == lst->begin)
		lst->begin = nx;
	return nx;
}

void
print_linked_list(Node* ptr)
{
	return;
}

int
main(void)
{
	static List beads;
	int c;

	(void) freopen("beads.in", "r", stdin);
	(void) freopen("beads.out","w",stdout);

	Init(&beads);

	while (c = getchar(), c != EOF) {
		if (c == '\n' || c == ' ')
			continue;

		switch (c) {
			case 'D': /* D for delete */
				Delete(&beads, beads.HEAD);
				break;
			case 'I': /* I for insert */
				while (c = getchar(), c == ' ');
				Insert(&beads, beads.HEAD->prev, c);
				break;
			case 'M':
				break;
		}
	}
	return 0;
}
// vim:foldmethod=marker:
